package com.zyk.problem;

import com.zyk.leetcode.TreeNode;
import com.zyk.util.TreeUtil;

/**
 * @author zhangsan
 * @date 2021/5/3 14:32
 */
public class MaxPathSumInBT {

    // 从头出发
    public static int maxSum(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        return process(root, 0);
    }

    public static int process(TreeNode cur, int pre) {
        if (cur.left == null && cur.right == null) return pre + cur.val;
        int l = Integer.MIN_VALUE;
        int r = Integer.MIN_VALUE;
        pre += cur.val;
        if (cur.left != null) {
            l = process(cur.left, pre);
        }
        if (cur.right != null) {
            r = process(cur.right, pre);
        }
        return Math.max(l, r);
    }

    // 从任意节点出发, 到根节点.最大路径
    public static int maxSum2(TreeNode root) {
        return c2(root);
    }

    public static int c2(TreeNode cur) {
        if (cur == null) return 0;
        int l = c2(cur.left);
        int r = c2(cur.right);
        int m = maxSum(cur);
        return Math.max(l, Math.max(r, m));
    }

    // 3: 可以从任意点出发, 只能向下走, 可以在任意节点停止
    public static int maxSum3(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        return process3_(root, 0);
    }

    // 1. 从之前开始.
    // 2. 从这里开始
    // 3. 到这里停的结果.
    // 4. 往后走的结果
    public static int process3(TreeNode cur, int pre) {
        if (cur == null) {
            return pre;
        }
        // 从之前开始, 往后走
        int p1 = process3(cur.left, pre + cur.val);
        int p2 = process3(cur.right, pre + cur.val);
        // 从这里开始, 往后走
        int p3 = process3(cur.left, cur.val);
        int p4 = process3(cur.right, cur.val);
        // 从之前到这里停. 从这里开始到这里停也就是只有他自己
        int p5 = pre + cur.val;
        int p6 = cur.val;
        return Math.max(Math.max(Math.max(p1, p2), Math.max(p3, p4)), Math.max(p5, p6));
    }

    public static int process3_(TreeNode cur, int pre) {
        if (cur == null) {
            return pre;
        }
        // 从之前到这里停. 从这里开始到这里停也就是只有他自己
        int preStartThisStop = pre + cur.val;
        int thisStartThisStop = cur.val;
        int bestStart = Math.max(preStartThisStop, thisStartThisStop);   // 这个值, 代表之前开始和现在开始哪儿个大(结束位置), 并且还代表后序的最优开始地方.
        // 从当前和之前选个最大值, 往后走
        int lGo = process3_(cur.left, bestStart);
        int rGo = process3_(cur.right, bestStart);
        return Math.max(Math.max(lGo, rGo), bestStart);
    }


    // 4. 可以从任意结点出发, 可以往下也可以往上走, 可以到达任意节点, 且至少包含一个节点
    public static int maxSum4(TreeNode root) {
        return process4(root).maxPathSum;
    }

    // 1: 与当前节点无关, 左右求个最大
    // 2: 与当前节点有关
    //      1): 左边最大+自己
    //      2): 右边最大+自己
    //      1): 自己
    //      1): 左边最大+右边最大+自己
    private static Info process4(TreeNode root) {
        if (root == null) {
            return new Info(-10001, -10001);
        }
        Info left = process4(root.left);
        Info right = process4(root.right);
        int p1 = Math.max(left.maxPathSum, right.maxPathSum);

        int p2 = root.val;
        int p3 = left.oneDirectionMaxPath + p2;
        int p4 = right.oneDirectionMaxPath + p2;

        int p5 = left.oneDirectionMaxPath + right.oneDirectionMaxPath + p2;

        int oneDirectionMaxPath = Math.max(p2, Math.max(p3, p4));
        int maxPathSum = Math.max(Math.max(p1, p5), oneDirectionMaxPath);
        return new Info(oneDirectionMaxPath, maxPathSum);
    }

    public static class Info {
        int maxPathSum;             // 包括它能走的最大路径
        int oneDirectionMaxPath;    // 包括自己往一侧走的最大路径

        public Info(int oneDirectionMaxPath, int maxPathSum) {
            this.oneDirectionMaxPath = oneDirectionMaxPath;
            this.maxPathSum = maxPathSum;
        }
    }


    public static void main(String[] args) {
        /*TreeNode root = new TreeNode(-3);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(9);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.left = new TreeNode(-10);
        root.right.right = new TreeNode(4);

        System.out.println(maxSum(root));
        System.out.println(maxSum2(root));
        System.out.println(maxSum3(root));
        System.out.println(maxSum4(root));*/

        /*TreeNode root = new TreeNode(-3);
        root.left = new TreeNode(-5);
        System.out.println(maxSum(root));*/

//        Integer[] arr = {-10, 9, 20, null, null, 15, 7};
//        Integer[] arr = {-3};
        Integer[] arr = {5,4,8,11,null,13,4,7,2,null,null,null,1};
        TreeNode root = TreeUtil.generateTreeByArr(arr);
        System.out.println(maxSum4(root));
    }

}
